#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-11-10 9:09 上午
# @Author  : yangdy
# @File    : 2020-11-10.31.下一个排列
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return
        # print(nums)
        p = True
        for i in range(len(nums)-2, -1, -1):
            m, mi, x = -1, -1, nums[i]
            for j in range(i+1, len(nums)):
                if nums[j] > nums[i] and (mi == -1 or nums[j] < m):
                    mi, m = j, nums[j]
            if mi != -1:
                nums[i], nums[mi] = nums[mi], nums[i]
                u = nums[i+1:]
                u.sort()
                nums[i+1:] = u
                p = False
                break
        if p:
            nums.sort()
        # print(nums)


questions = [
    ([1, 2, 3],),
    ([3, 2, 1],),
    ([1, 1, 5],),
    ([1, 3, 2],),
]

work(questions, lambda q:Solution().nextPermutation(q[0]))

